package leetcode.D700.T647;

class Solution {
    // 一刷
    // 解法一：朴素动态规划，时间复杂度：O(n2)，空间复杂度：O(n2)
    /*public int countSubstrings(String s) {
        boolean[][] dp = new boolean[s.length()][s.length()];
        int result = s.length();
        for(int i=0; i<s.length(); ++i) {
            dp[i][i] = true;
            if(i > 0 && s.charAt(i-1) == s.charAt(i)) {
                dp[i-1][i] = true;
                result++;
            }
        }
        for(int step=2; step < s.length(); ++step) {
            for(int i=0; i+step<s.length(); ++i) {
                int j = i + step;
                if(dp[i+1][j-1] && s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = true;
                    result++;
                }
            }
        }
        return result;
    }*/

    // 解法二：中心扩展法
    // 时间复杂度：O(n2)，空间复杂度：O(1)
    /*public int countSubstrings(String s) {
        int result = s.length();
        for(int i=0; i<s.length(); ++i) {
            int step = 1;
            while(i - step >= 0 && i + step < s.length()) {
                if(s.charAt(i-step) != s.charAt(i+step)) {
                    break;
                }
                result++;
                step++;
            }
        }
        for(int i=1; i<s.length(); ++i) {
            int step = 1;
            while(i-step >= 0 && i + step - 1 < s.length()) {
                if(s.charAt(i-step) != s.charAt(i+step-1)) {
                    break;
                }
                result++;
                step++;
            }
        }
        return result;
    }*/

    // 二刷
    public int countSubstrings(String s) {
        int ans = s.length();
        for (int i=0; i<s.length(); ++i) {
            int step = 1;
            while (i - step >= 0 && i + step < s.length()) {
                if (s.charAt(i - step) != s.charAt(i + step))
                    break;
                ans++;
                step++;
            }
        }
        for (int i=0; i<s.length(); ++i) {
            int step = 0;
            while (i - step >= 0 && i + 1 + step < s.length()) {
                if (s.charAt(i - step) != s.charAt(i + 1 + step))
                    break;
                ans++;
                step++;
            }
        }
        return ans;
    }
}
